package _02array;

public class _07DeleteSortArray {
    public static void main(String[] args) {
        int i;
        int[] arr = new int[]{ 1, 4, 7, 10, 15, 19, 22, 30, 31 };

        int capacity = arr.length;

        // delete 10
        int target = 10;
        capacity = deleteElement(arr, capacity, target);

        System.out.print("after delete: ");
        for (i = 0; i < capacity; ++i)
            System.out.println(arr[i] + " ");

    }
    private static int deleteElement(int arr[], int capacity, int target) {
        // find position of element to be deleted
        int pos = binarySearch(arr, 0, capacity - 1, target);

        if (pos == -1) {
            System.out.println("target not found");
            return capacity;
        }

        // delete target
        for (int i = pos; i < capacity - 1; ++i)
            arr[i] = arr[i + 1];

        return capacity - 1;
    }

    // binary search
    // time complexity: O(log(n))
    // space complexity: O(1)
    private static int binarySearch(int arr[], int l, int r, int target) {
        while(l <= r) {
            int mid = l + (r - l) / 2;
            // arr[mid] 等于 target
            if(arr[mid] ==  target)
                return mid;
            else if(arr[mid] > target)  // target在左边
                r = mid - 1;
            else
                l = mid + 1;   // target在右边
        }
        return -1;
    }
}
